﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

public class SolMihayo2
{
    public int maxProfit = 0;
    bool[] cantJoin;
    public  int MyMaxProfit(int[] vol, int[] profit,int packageVol, IList<IList<int>> huchi )
    {

        //回溯
        cantJoin = new bool[vol.Length];    
            DFS(0, vol, profit, packageVol, 0, huchi);
        return maxProfit;


    }
    

    private void DFS(int start, int[] vol, int[] profit, int packageVol,int curProfit, IList<IList<int>> huchi)
    {

        for (int i = start; i < vol.Length; i++)//递归中止条件隐藏在这里
        {
            //判断背包里面有没有互斥的
            //每次加入一个新的物品，就更新一个数组，这个数组被标记的就不可以加入

            Console.WriteLine(cantJoin[i]);
            if (!cantJoin[i] &&packageVol >= vol[i])
            {

                for(int j = 0; j < huchi[i+1].Count; j++)//与i互斥的全部设置为不可加入
                {
                  int index1=  huchi[i+1][j]-1;
                    Console.WriteLine(index1);
                    cantJoin[index1] = true;
                }
                curProfit += profit[i];
                Console.WriteLine("curProfit" + curProfit);
                maxProfit = Math.Max(maxProfit, curProfit);

                DFS(i + 1, vol, profit, packageVol - vol[i], curProfit, huchi);
                //回溯
                curProfit -= profit[i];

                for (int j = 0; j < huchi[i+1].Count; j++)//与i互斥的全部设置为不可加入
                {
                    int index2 = huchi[i +1][j] - 1;
                    cantJoin[index2] = false;
                }
            }


            

        }
    }
}


public class ProgramMihayo2
{
    public static void MainMihayo2()
    {
        string line;


        //while ((line = Console.ReadLine()) != null)
        //{ // 注意 while 处理多个 case
        //    string[] tokens = line.Split();

        //    int n = int.Parse(tokens[0]);//商品数量
        //    int m = int.Parse(tokens[1]);//背包
        //    int k = int.Parse(tokens[2]);//互斥

        //    int[] vol=new int[n];
        //    int[] profit=new int[n];


        //    for (int i = 0; i < n; i++)
        //    {
        //        line = Console.ReadLine();
        //        tokens = line.Split();
        //        vol[i]= int.Parse(tokens[0]);
        //        profit[i]= int.Parse(tokens[1]);


        //    }
        //    //互斥关系使用list存放
        //    IList<IList<int>> huchi = new List<IList<int>>();
        //    for (int i = 0; i < n; i++)
        //    { 
        //    huchi.Add(new List<int>());
        //    }
        //        for (int i = 0; i < k; i++)
        //    {

        //        line = Console.ReadLine();
        //        tokens = line.Split();
        //        int a = int.Parse(tokens[0]);
        //        int b= int.Parse(tokens[1]);
        //        huchi[a].Add(b);
        //huchi[b].Add(a);


        //    }

        //    //System.Console.WriteLine(int.Parse(tokens[0]) + int.Parse(tokens[1]));

        //    SolMihayo2 sol = new SolMihayo2();

        //    vol = [15, 20, 15];
        //    profit = [19, 30, 19];


        //    int res = sol.MyMaxProfit(vol, profit, m, huchi);

        //    Console.WriteLine("res" + res);
        //}

        SolMihayo2 sol = new SolMihayo2();

       int[] vol = [15, 20, 15];
      int[]  profit = [19, 30, 19];
        int m = 100;
      
        //互斥关系使用list存放
        IList<IList<int>> huchi = new List<IList<int>>();
        for (int i = 0; i < 4; i++)
        {
            huchi.Add(new List<int>());
        }

        huchi[1].Add(2);
        huchi[2].Add(3);
        huchi[2].Add(1);


        int res = sol.MyMaxProfit(vol, profit, m, huchi);

        Console.WriteLine("res" + res);
    }
}

//3 100 2
//15 19
//20 30
//15 19
//1 2
//2 3


//38